{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #斐波那契数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #memoization #math #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #记忆化搜索 #数学 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: fib"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #斐波那契数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p><strong>斐波那契数</strong> （通常用 <code>F(n)</code> 表示）形成的序列称为 <strong>斐波那契数列</strong> 。该数列由 <strong>0</strong> 和 <strong>1</strong> 开始，后面的每一项数字都是前面两项数字的和。也就是：</p>\n",
    "\n",
    "<pre>\n",
    "F(0) = 0，F(1) = 1\n",
    "F(n) = F(n - 1) + F(n - 2)，其中 n &gt; 1\n",
    "</pre>\n",
    "\n",
    "<p>给定 <code>n</code> ，请计算 <code>F(n)</code> 。</p>\n",
    "\n",
    "<p>答案需要取模 1e9+7(1000000007) ，如计算初始结果为：1000000008，请返回 1。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 2\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>F(2) = F(1) + F(0) = 1 + 0 = 1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 3\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>F(3) = F(2) + F(1) = 1 + 1 = 2\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 4\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>F(4) = F(3) + F(2) = 2 + 1 = 3\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= n &lt;= 100</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [fei-bo-na-qi-shu-lie-lcof](https://leetcode.cn/problems/fei-bo-na-qi-shu-lie-lcof/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [fei-bo-na-qi-shu-lie-lcof](https://leetcode.cn/problems/fei-bo-na-qi-shu-lie-lcof/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['2', '3', '4']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        a, b = 0, 1\n",
    "        for _ in range(n):\n",
    "            a, b = b, a + b\n",
    "        return a % 1000000007\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        a, b = 0, 1\n",
    "        for _ in range(n):\n",
    "            a, b = b, (a + b)\n",
    "        return a%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        x1,x2=0,1\n",
    "        for _ in range(n):\n",
    "            x1,x2=x2,x1+x2\n",
    "        return x1  % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        elif n == 1:\n",
    "            return 1\n",
    "        else :\n",
    "            a, b = 0, 1\n",
    "            for i in range(n-1):\n",
    "                a, b = b, a + b\n",
    "            return b%(1000000007)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        if n==0:\n",
    "            return 0\n",
    "        dp = [0] * (n+1)\n",
    "        dp[1] = 1\n",
    "        for i in range(2,n+1):\n",
    "            dp[i] = dp[i-1]+dp[i-2]\n",
    "            dp[i] %= 1000000007\n",
    "        return dp[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        if n <= 1:\n",
    "            return n\n",
    "        dp = [0] * (n + 1)\n",
    "        dp[0] = 0\n",
    "        dp[1] = 1\n",
    "        for i in range(2, n + 1):\n",
    "            dp[i] = dp[i - 1] + dp[i - 2]\n",
    "        return dp[n] % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        if n==0:\n",
    "            return 0\n",
    "        if n==1:\n",
    "            return 1\n",
    "        a,b = 0, 1\n",
    "        for i in range(2, n+1):\n",
    "            res = a + b\n",
    "            a = b\n",
    "            b = res\n",
    "        \n",
    "        return res%(1000000007)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        if n == 0: return 0\n",
    "        dp = [0] * (n+1)\n",
    "        dp[0], dp[1] = 0, 1\n",
    "        for i in range(2, n+1):\n",
    "            dp[i] = dp[i-1] + dp[i-2]\n",
    "        return dp[n]%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        if n==0: \n",
    "            return 0\n",
    "        if n==1 or n==2:\n",
    "            return 1\n",
    "        dep=[0]*n\n",
    "        dep[0]=1\n",
    "        dep[1]=1\n",
    "        for index in range(2,n):\n",
    "            dep[index]=(dep[index-2]+dep[index-1])%1000000007\n",
    "        return dep[n-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        if n<=1:\n",
    "            return n\n",
    "        else:\n",
    "            x=0\n",
    "            y=1\n",
    "            for i in range(2,n+1): #2,3,4\n",
    "                s=x+y\n",
    "                x=y\n",
    "                y=s\n",
    "            return y%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        if n < 3:\n",
    "            return 1\n",
    "        p1 = 1\n",
    "        p2 = 1\n",
    "        p3 = 0\n",
    "        for i in range(2 , n):\n",
    "            p3 = (p1 + p2)%1000000007\n",
    "            p1 = p2\n",
    "            p2 = p3\n",
    "        return p3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        dp = [0,1]\n",
    "        for i in range(2,n+1):\n",
    "            num = (dp[i-1]+dp[i-2]) % 1000000007\n",
    "            dp.append(num)\n",
    "        print(dp)\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        ini0, ini1 = 0, 1\n",
    "        res = 0\n",
    "        cur = 1\n",
    "        if n == 0: return 0\n",
    "        for i in range(n-1):\n",
    "            kk = cur\n",
    "            cur = res + cur\n",
    "            res = kk     \n",
    "        return cur % 1000000007   #注意取模就是取余数\n",
    "        #return kk\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        if n==1 or n==0:\n",
    "            return n\n",
    "        dp=[0 for i in range(n+1)]\n",
    "        dp[1]=1\n",
    "        for i in range(2,n+1):\n",
    "            dp[i]=dp[i-2]+dp[i-1]\n",
    "        return dp[-1]%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        if n == 0: return 0\n",
    "        if n == 1: return 1\n",
    "        dp = [0] * (n+1)\n",
    "        dp[0],dp[1]= 0,1\n",
    "        for i in range(2,n+1):\n",
    "            dp[i] = dp[i-1] + dp[i-2]\n",
    "        return dp[n]%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        if n==1 or n==0:\n",
    "            return n\n",
    "        dp=[0 for i in range(n+1)]\n",
    "        dp[1]=1\n",
    "        for i in range(2,n+1):\n",
    "            dp[i]=dp[i-2]+dp[i-1]\n",
    "        return dp[-1]%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        if n == 0: return 0\n",
    "        if n == 1: return 1\n",
    "        dp = [0] * (n+1)\n",
    "        dp[0],dp[1]= 0,1\n",
    "        for i in range(2,n+1):\n",
    "            dp[i] = dp[i-1] + dp[i-2]\n",
    "        return dp[n]%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        if n == 0 or n == 1:\n",
    "            return n\n",
    "        MOD = 10 ** 9 + 7\n",
    "        a, b, c = 0,0,1\n",
    "        for _ in range(n-1):\n",
    "            a, b = b, c\n",
    "            c = (a + b) % MOD\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        a, b = 0, 1\n",
    "        for _ in range(n):\n",
    "            a, b = b, a + b\n",
    "        return a % 1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        dp = [0 for _ in range(n+1)]\n",
    "        dp[0] = 0\n",
    "        dp[1] = 1\n",
    "        for i in range(2, n+1):\n",
    "            dp[i] = dp[i-1] + dp[i-2]\n",
    "        return dp[n]%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        if n== 0:\n",
    "            return 0\n",
    "        dp= [0]*(n+1)\n",
    "        dp[0] = 0\n",
    "        dp[1] =1\n",
    "        for i in range(2,n+1):\n",
    "            dp[i] = dp[i-1]+dp[i-2]\n",
    "        return dp[-1]%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def fib(self, n: int) -> int:\r\n",
    "        if n == 0:\r\n",
    "            return 0\r\n",
    "        if n == 1:\r\n",
    "            return 1\r\n",
    "        lst = [0, 1]\r\n",
    "        for i in range(1, n):\r\n",
    "            lst.append(lst[-1] + lst[-2])\r\n",
    "        return lst[-1] % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        a=[0,1]\n",
    "        if n<2:return a[n]\n",
    "        for i in range(2,n+1):\n",
    "            a.append(a[-1]+a[-2])\n",
    "            a=a[-2:]\n",
    "        return a[-1]%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        if n==0:\n",
    "            return 0\n",
    "        if n==1:\n",
    "            return 1\n",
    "        MOD = 1e9+7\n",
    "        arr = [0,1]\n",
    "        for i in range(2,n+1):\n",
    "            arr.append((arr[i-1]+arr[i-2])%MOD)\n",
    "        \n",
    "        return int(arr[-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    memo = {0: 0, 1: 1}\n",
    "    def fib(self, n: int) -> int:\n",
    "        \n",
    "        if n < 2:\n",
    "            return n\n",
    "        # res = [0,1]\n",
    "        # for i in range(2,n+1):\n",
    "        #     res.append(res[-1]  +res[-2])\n",
    "        # return res[-1] % 1000000007\n",
    "        \n",
    "        \n",
    "    \n",
    "        if n not in self.memo:\n",
    "            self.memo[n] = self.fib(n - 1) + self.fib(n - 2)\n",
    "        return self.memo[n]% 1000000007\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        pre2, pre1 = 0, 1\n",
    "        for i in range(2, n + 1):\n",
    "            tmp = pre1\n",
    "            pre1 = pre1 + pre2\n",
    "            pre2 = tmp\n",
    "        return pre1 % (1000000007)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        if n == 0 or n == 1:\n",
    "            return n\n",
    "        a, b = 0, 1\n",
    "        for i in range(n - 1):\n",
    "            a, b = b, a + b\n",
    "        return b % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 不考虑大数越界问题\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        a, b = 0, 1\n",
    "        for _ in range(n):\n",
    "            a, b = b, a + b\n",
    "        return a % 1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        dp = [0] * (n+1)\n",
    "        if n < 2:\n",
    "            return n\n",
    "        dp[0] = 0\n",
    "        dp[1] = 1\n",
    "        for i in range(2,n+1):\n",
    "            dp[i] = dp[i-1] + dp[i-2]\n",
    "        \n",
    "        return dp[n]%1000000007\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        a, b = 0, 1\n",
    "        for _ in range(n):\n",
    "            a, b = b, a + b\n",
    "        return a % 1000000007\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        a,b=0,1\n",
    "        for _ in range(n):\n",
    "            a,b=b,a+b\n",
    "        return a%int(1e9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        dp = [0]*2\n",
    "        dp[0] = 0\n",
    "        dp[1] = 1\n",
    "        mod =  1e9+7\n",
    "        for i in range(2,n+1):\n",
    "            tmp = dp[0]+dp[1]\n",
    "            dp[0] = dp[1]\n",
    "            dp[1] = int(tmp%mod)\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        i, j = 0, 1\n",
    "        for k in range(n):\n",
    "            i, j = j%(1e9+7) , (i + j)%(1e9+7)\n",
    "        return int(i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self,n:int):\n",
    "        if n == 1 or n == 0:\n",
    "            return n\n",
    "        p,q,r,z = 0,1,1,(10**9+7)\n",
    "        for i in range(2,n):\n",
    "            p = q\n",
    "            q = r\n",
    "            r = (p + q) % z\n",
    "        return r \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        elif n <= 2:\n",
    "            return 1\n",
    "        a, b = 0, 1\n",
    "        for i in range(1,n):\n",
    "            a, b = b, a + b\n",
    "        return b % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        a,b = 0,1\n",
    "        for _ in range(n):\n",
    "            a,b = b,a+b\n",
    "        return a%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        if n<0:\n",
    "            return -1\n",
    "        elif n==0:\n",
    "            return 0;\n",
    "        elif n==1:\n",
    "            return 1;\n",
    "        else:\n",
    "            dp = []\n",
    "            dp.append(0)\n",
    "            dp.append(1)\n",
    "            for i in range(2,n+1):\n",
    "                dp_tmp = (dp[i-1] + dp[i-2])%1000000007\n",
    "                dp.append(dp_tmp)\n",
    "            return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        a, b = 0, 1\n",
    "        for _ in range(n):\n",
    "            a, b = b, (a + b) % 1000000007\n",
    "        return a\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        if n==0:\n",
    "            return 0\n",
    "        F=[0 for _ in range(n+1)]\n",
    "        mod=10**9+7\n",
    "        F[0]=0\n",
    "        F[1]=1\n",
    "        for i in range(2,n+1):\n",
    "            # F[i]=int((F[i-1]+F[i-2])%(1e9+7))\n",
    "            F[i]=(F[i-1]+F[i-2])%mod\n",
    "        return F[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        elif n == 1:\n",
    "            return 1\n",
    "        dp = [0, 1] + [0] * (n - 1)\n",
    "        for i in range(2, len(dp)):\n",
    "            dp[i] = dp[i-1] + dp[i-2]\n",
    "        return dp[-1] % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        dp = [0] * 101\n",
    "        dp[0] = 0\n",
    "        dp[1] = 1\n",
    "        dp[2] = 1\n",
    "        dp[3] = 2\n",
    "        \n",
    "        for i in range(4,n+1):\n",
    "            dp[i] = dp[i-1] + dp[i-2]\n",
    "\n",
    "        \n",
    "        return dp[n] if dp[n] < 1000000007 else dp[n]%1000000007\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 不考虑大数越界问题\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        a, b = 0, 1\n",
    "        for _ in range(n):\n",
    "            a, b = b, a + b\n",
    "        return a % 1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        if n == 1:\n",
    "            return 1\n",
    "\n",
    "        f0 = 0\n",
    "        f1 = 1\n",
    "        for i in range(2, n+1):\n",
    "            f = f0 + f1\n",
    "            f0 = f1\n",
    "            f1 = f\n",
    "        return f % int(1e9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        # 别动\n",
    "\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        elif n == 1:\n",
    "            return 1\n",
    "        elif n > 1:\n",
    "            a = 0\n",
    "            b = 1\n",
    "            c = 0\n",
    "            for i in range(1,n):\n",
    "                c = a + b\n",
    "                a = b\n",
    "                b = c\n",
    "            return c % 1000000007\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        a, b = 0, 1\n",
    "        for index in range(n): \n",
    "            a, b = b, a+b\n",
    "        return a % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "            arr = []\n",
    "            for i in range(0, n+1):\n",
    "                if i == 0:\n",
    "                    arr.append(0)\n",
    "                    \n",
    "                elif i == 1:\n",
    "                    \n",
    "                    arr.append(1)\n",
    "                elif i == 2:\n",
    "                    \n",
    "                    arr.append(1)\n",
    "                else:\n",
    "                    n1 = arr[i-1]\n",
    "                    n2 = arr[i-2]\n",
    "                    arr.append(n2 + n1)\n",
    "\n",
    "\n",
    "            return arr[n] % 1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        cur, next = 0, 1\n",
    "        for i in range(n):\n",
    "            cur, next = next, cur + next\n",
    "        return cur % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        a,b=0,1\n",
    "        for i in range(n):\n",
    "            a,b=b,(a+b)%1000000007\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        \n",
    "        result = 0\n",
    "        one_step_pre = 1\n",
    "        two_step_pre = 0\n",
    " \n",
    "        for i in range(2, n+1):\n",
    "            one_step_pre, two_step_pre = (one_step_pre + two_step_pre) % MOD, one_step_pre\n",
    "            \n",
    "        return one_step_pre"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        if n==0:\n",
    "            return 0\n",
    "        if n==1:\n",
    "            return 1\n",
    "        res=0\n",
    "        pre=1\n",
    "        prepre=0\n",
    "        for i in range(2,n+1):\n",
    "            res=pre+prepre\n",
    "            prepre=pre\n",
    "            pre=res\n",
    "        return res%1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        fibSeries = [-1 for _ in range(n+1)]\n",
    "        for i in range(n+1):\n",
    "            if i == 0:\n",
    "                fibSeries[i] = 0\n",
    "                continue\n",
    "            if i == 1:\n",
    "                fibSeries[i] = 1\n",
    "                continue\n",
    "            fibSeries[i] = fibSeries[i-1] + fibSeries[i-2]\n",
    "        \n",
    "        return fibSeries[-1] % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        a=1\n",
    "        b=1\n",
    "        if n==0:\n",
    "            return 0\n",
    "        if n==1 or n==2:\n",
    "            return 1\n",
    "        for i in range(n-2):\n",
    "            a,b=b,a+b\n",
    "        return b%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        li = [0, 1, 1]\n",
    "        for i in range(3, n+1):\n",
    "            f1 = li[-1]\n",
    "            f2 = li[-2]\n",
    "            li.append(f1+f2)\n",
    "        return li[n] % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        a,b=[1,1],0\n",
    "        if not n:return 0\n",
    "        if n<3:return 1\n",
    "        for i in range(n-2):\n",
    "            b=1-b\n",
    "            a[b]=a[0]+a[1]\n",
    "        return a[b]%1000000007\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        elif n == 1:\n",
    "            return 1\n",
    "        p, q = 0, 1\n",
    "        for i in range(2, n + 1):\n",
    "            tmp = p\n",
    "            p = q\n",
    "            q = tmp + p\n",
    "        if q > 1e9 + 7:\n",
    "            return q % MOD\n",
    "        else:\n",
    "            return q"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        if n<2:\n",
    "            return n\n",
    "        p,q,r = 0,0,1\n",
    "        for i in range(2, n+1):\n",
    "            p=q\n",
    "            q=r\n",
    "            r=(p+q)%mod\n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        MOD = 1000000007\n",
    "\n",
    "        # Base cases\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        if n == 1:\n",
    "            return 1\n",
    "\n",
    "        # Initializing the first two Fibonacci numbers\n",
    "        a, b = 0, 1\n",
    "\n",
    "        # Iteratively calculating the nth Fibonacci number\n",
    "        for _ in range(2, n + 1):\n",
    "            a, b = b, (a + b) % MOD\n",
    "\n",
    "        return b\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "            a=[0]*101\n",
    "            a[0]=0\n",
    "            a[1]=1\n",
    "            for i in range(2,101):\n",
    "                a[i]=a[i-1]+a[i-2]\n",
    "            return a[n]%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "r=[0,1,1,2]\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "      if n<len(r):\n",
    "        return r[n]\n",
    "      for i in range(len(r),n+1):\n",
    "        r.append(sum(r[-2:]))\n",
    "      return r[n]%1000000007\n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        first, second = 0, 1\n",
    "        for i in range(2, n + 1):\n",
    "            first, second = second, first + second\n",
    "        return second % 1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        if n == 0:return 0\n",
    "        a = 0\n",
    "        b = 1\n",
    "        for i in range(n):\n",
    "            a,b = b,(a+b)\n",
    "        return a % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        i, j = 0, 1\n",
    "        for x in range(n):\n",
    "            i, j = j, i + j\n",
    "        return i % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        fibSeries = [-1 for _ in range(n+1)]\n",
    "        for i in range(n+1):\n",
    "            if i == 0:\n",
    "                fibSeries[i] = 0\n",
    "                continue\n",
    "            if i == 1:\n",
    "                fibSeries[i] = 1\n",
    "                continue\n",
    "            fibSeries[i] = fibSeries[i-1] + fibSeries[i-2]\n",
    "        \n",
    "        return fibSeries[-1] % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        if n==0:\n",
    "            return 0\n",
    "        if n==1:\n",
    "            return 1\n",
    "        dp=[0]*(n+1)\n",
    "        dp[1]=1\n",
    "        for i in range(2,n+1):\n",
    "            dp[i]=dp[i-1]+dp[i-2]\n",
    "        return dp[n]%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        # DPS的问题\n",
    "        fib0,fib1 = 1,1\n",
    "        if n ==0:\n",
    "            return 0\n",
    "        for i in range(n-2):\n",
    "            newNumber = fib0+fib1\n",
    "            fib0 = fib1\n",
    "            fib1 = newNumber\n",
    "        return fib1%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        dp = [0,1, 1]\n",
    "        if n<3:\n",
    "            return dp[n]\n",
    "        for i in range(3,n+1):\n",
    "            num = dp[i-1]+dp[i-2]\n",
    "            num%=1000000007\n",
    "            dp.append(num)\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        a, b = 0, 1\n",
    "        for _ in range(n):\n",
    "            a, b = b, (a + b) % 1000000007\n",
    "        return a\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        f1 = 0\n",
    "        f2 = 1\n",
    "        if n == 0:\n",
    "            return f1\n",
    "        for i in range(2, n+1):\n",
    "            f1, f2 = f2, f1+f2\n",
    "        return f2%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        if n < 2:\n",
    "            return n\n",
    "        p, q, r = 0, 0, 1\n",
    "        for i in range(2, n + 1):\n",
    "            p = q\n",
    "            q = r\n",
    "            r = (p + q) % MOD\n",
    "        return r\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        max_num = 1000000007\n",
    "        fn_prev = 0\n",
    "        fn = 1\n",
    "        if n==0 or n==1:\n",
    "            return n\n",
    "        for i in range(2,n+1):\n",
    "            temp = fn\n",
    "            fn = (fn+fn_prev)%max_num\n",
    "##            print(i,fn)\n",
    "            fn_prev = temp\n",
    "        return fn\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        max_num = 1000000007\n",
    "        fn_prev = 0\n",
    "        fn = 1\n",
    "        if n==0 or n==1:\n",
    "            return n\n",
    "        for i in range(2,n+1):\n",
    "            fn = (fn+fn_prev)%max_num\n",
    "##            print(i,fn)\n",
    "            fn_prev = fn-fn_prev\n",
    "        return fn\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        if n==0:return 0\n",
    "        if n==1:return 1\n",
    "        f= [0]*(n+1)\n",
    "        f[0]=0\n",
    "        f[1]=1\n",
    "        for i in range(2,n+1):\n",
    "            f[i]=f[i-1]+f[i-2]\n",
    "        return f[n]%1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        nums = [0, 1]\n",
    "        while len(nums) <= n :\n",
    "            nums.append(nums[-1] + nums[-2])\n",
    "        return nums[n] % (1000000007)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        if n <= 1:\n",
    "            return n\n",
    "        \n",
    "        MOD = 1000000007 \n",
    "\n",
    "        a, b = 0, 1\n",
    "\n",
    "        for _ in range(2, n + 1):\n",
    "            a, b = b, (a + b) % MOD  \n",
    "        \n",
    "        return b\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def fib(self, n: int) -> int:\n",
    "#         MOD = 1000000007\n",
    "\n",
    "#         # Base cases\n",
    "#         if n == 0:\n",
    "#             return 0\n",
    "#         if n == 1:\n",
    "#             return 1\n",
    "\n",
    "#         # Initializing the first two Fibonacci numbers\n",
    "#         a, b = 0, 1\n",
    "\n",
    "#         # Iteratively calculating the nth Fibonacci number\n",
    "#         for _ in range(2, n + 1):\n",
    "#             a, b = b, (a + b) % MOD\n",
    "\n",
    "#         return b\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        a = 0\n",
    "        b = 1\n",
    "        c = 1\n",
    "        for i in range(n-1):\n",
    "            c = a + b\n",
    "            a = b\n",
    "            b = c\n",
    "        return c % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        if n <= 1:return n\n",
    "        a, b = 0, 1\n",
    "        for i in range(2, n+1):\n",
    "            a, b = b, (a+b) % 1000000007\n",
    "        return b"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
